
import FIFO::*;
import ConfigReg::*;
import RWire::*;

import List::*;
//import Monad::*;

interface SFIFO#(type alpha_T, type search_T);
   method Action enq(alpha_T x);
   method Action deq();
   method alpha_T first();
   method Action clear();
   method Bool find(search_T x);   
   method Bool find2(search_T x);
   method Bool notEmpty();
   method Bool notFull();
endinterface

module mkSFIFO#(function Bool searchfunc(search_T s, alpha_T x)) (SFIFO#(alpha_T, search_T))
    provisos
      (Bits#(alpha_T,asz));

    Reg#(alpha_T) f0 <- mkConfigRegU;
    Reg#(alpha_T) f1 <- mkConfigRegU;

    Reg#(Bool)   vf0 <- mkConfigReg(False);
    Reg#(Bool)   vf1 <- mkConfigReg(False);

    PulseWire edge1      <- mkPulseWire();
      
    method Action enq(alpha_T x) if (!(vf0 && vf1));
      if (edge1 || !vf0)//empty or we're dequeueing
	begin
          vf0 <= True; //True
	  vf1 <= False;
	   f0 <= x;
  	end
      else // !vf1 
        begin
          vf1 <= True;
           f1 <= x;
 	end
    endmethod
										
    method Action deq() if (vf0);
      edge1.send();
      vf0 <= vf1;
       f0 <= f1;
      vf1 <= False;
    endmethod  

    method alpha_T first() if(vf0);
      return (f0);
    endmethod  

    method Action clear();
      vf0 <= False;
      vf1 <= False;
    endmethod

    method Bool find(search_T sv);
      Bool nvf0 = edge1 ? False: vf0;
      Bool nvf1 = vf1;

      return (nvf0 && searchfunc(sv, f0) || 
              nvf1 && searchfunc(sv, f1));
    endmethod

    method Bool find2(search_T sv);
      Bool nvf0 = edge1 ? False: vf0;
      Bool nvf1 = vf1;
      
      return (nvf0 && searchfunc(sv, f0) || 
              nvf1 && searchfunc(sv, f1));
    endmethod

    method notEmpty() = vf0._read;

    method Bool notFull();
      return !(vf0 && vf1);
    endmethod

endmodule

module mkSFIFO1#(function Bool searchfunc(search_T s, alpha_T x)) (SFIFO#(alpha_T, search_T))
    provisos
      (Bits#(alpha_T,asz), Eq#(alpha_T));

    Reg#(alpha_T) f0 <- mkConfigRegU;

    Reg#(Bool)   vf0 <- mkConfigReg(False);

    PulseWire edge1      <- mkPulseWire();
      
    method Action enq(alpha_T x) if (!vf0);
      vf0 <= True; //True
      f0 <= x;
    endmethod
										
    method Action deq() if (vf0);
      edge1.send();
      vf0 <= False;
    endmethod  

    method alpha_T first() if(vf0);
      return (f0);
    endmethod  

    method Action clear();
      vf0 <= False;
    endmethod

    method Bool find(search_T sv);
      Bool nvf0 = edge1 ? False: vf0;

      return (nvf0 && searchfunc(sv, f0));
    endmethod

    method Bool find2(search_T sv);
      Bool nvf0 = edge1 ? False: vf0;
      return (nvf0 && searchfunc(sv, f0));
    endmethod

    method notEmpty() = vf0._read;

    method Bool notFull();
      return !vf0;
    endmethod

endmodule

module mkSizedSFIFOInternal#(Integer n, 
			     function Bool searchfunc1(search_T s, alpha_T x), 
			     function Bool searchfunc2(search_T s, alpha_T x))  (SFIFO#(alpha_T, search_T))
				
   provisos ( Bits#(alpha_T,alpha_SZ) );

  List#(Reg#(alpha_T)) registers <- replicateM(n, mkRegU);
  List#(Reg#(Bool))   valids <- replicateM(n, mkReg(False));

  function Nat getNextFree (List#(Reg#(Bool)) vs);

    Nat res = fromInteger(n - 1);

    for (Integer x = n - 1; x > -1; x = x - 1)
      res = !vs[x]._read() ? fromInteger(x) : res;

    return res;
  
  endfunction

  function Bool notFullHelper();
  
    Bool full = True;

    for (Integer x = 0; x < n; x = x + 1)
      full = full && valids[x]._read();

    return !full;
  
  endfunction

  method Action enq( alpha_T item ) if ( notFullHelper() );
    
    Nat k = getNextFree(valids);
    select(valids, k)._write(True);
    select(registers, k)._write(item);
    
  endmethod

  method Action deq() if ( valids[0]._read() );
    
    for (Integer x = 0; x < (n-1); x = x + 1)
    begin
    
      (registers[x]) <= registers[x + 1]._read();
      (valids[x]) <= valids[x + 1]._read();
    
    end
    (valids[n-1]) <= False;
  endmethod  

  method alpha_T first() if ( valids[0]._read() );
    return registers[0]._read();  
  endmethod

  method Bool find(search_T sv);
    Bool res = False;
    
    for (Integer x = 0; x < n; x = x + 1)
       if ( valids[x]._read() && searchfunc1(sv, registers[x]._read()) )
          res = True;
    
    return res;
    
  endmethod

  method Bool find2(search_T sv);
    Bool res = False;
    
     for (Integer x = 0; x < n; x = x + 1)
        if ( valids[x]._read() && searchfunc2(sv, registers[x]._read()) )
           res = True;
    
    return res;
    
  endmethod

  method Action clear();
  
    for (Integer x = 0; x < n; x = x + 1)
      (valids[x]) <= False;
    
  endmethod

  method Bool notEmpty();
    return valids[0]._read(); 
  endmethod

  method Bool notFull();
    return notFullHelper();
  endmethod

endmodule

module mkSizedSFIFO#(Integer n, function Bool searchfunc(search_T s, alpha_T x))  (SFIFO#(alpha_T, search_T))
    provisos
      (Bits#(alpha_T,asz));
   
   let foo <- mkSizedSFIFOInternal(n, searchfunc, searchfunc);
   return foo;

endmodule
